package org.example.dp.split;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/05/16 19:10
 */
public class Solution139 {


    public static void main(String[] args) {

        Solution139 solution139 = new Solution139();
        String s = "leetcode";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        System.out.println(solution139.wordBreak(s, wordDict));
    }

    //dp[i] 表示 i-word.len , i word? && dp[i-word.len-1] = true
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for(int i=1;i<=n;i++){
            for(String word : wordDict){
                int len = word.length();
                if(i>=len && word.equals(s.substring(i-len, i))){
                    // dp[i] 可以有多个单词的组合场景，任一满足即可
                    dp[i] = dp[i] || dp[i-len];
                }
            }
        }

        return dp[n];
    }

}
